//题目:
// 你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示， 在这个矩阵中：
// 0 表示障碍，无法触碰
// 1 表示地面，可以行走
// 比 1 大的数 表示有树的单元格，可以行走，数值表示树的高度
// 每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。
// 你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。
// 你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 -1 。
// 可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。
#include<iostream>
#include<queue>
#include<unordered_map>
#include<string.h>
#include<algorithm>

using namespace std;
//代码:
class Solution 
{
    //方向矢量:上、下、左、右
    int arr_x[4]={-1,1,0,0},arr_y[4]={0,0,-1,1};
public:
    // int cutOffTree(vector<vector<int>>& forest) 
    // {
    //     //题目要求:1.先砍低的树，再砍高的树;  2.将树砍倒后，单元格的值改为1;  3.0不能走，非0才能走
    //     //思路:bfs，队列每层存放"非0的相邻单元格",按值大小排升序,直到无路可走,判断树是否已经全部砍完
        
    //     //1.给所有树按高度排序
    //     vector<int> v;
    //     for(int i=0;i<forest.size();i++)
    //     {
    //         for(int j=0;j<forest[i].size();j++)
    //         {
    //             if(i==0 && j==0); //(0,0)单元格值不入v

    //             else if(forest[i][j]!=0)
    //                     v.push_back(forest[i][j]);
    //         }
    //     }
    //     sort(v.begin(),v.end());
        
    //     //接下来,需要从forest中依次找到pq中的值,每次都按最小路径去找

    //     //4.记录所有v[i]的最短路径
    //     int ret=0,next_x=0,next_y=0;
    //     int k=0;
    //     start:
    //     while(k<v.size())
    //     {
    //         set<pair<int,int>> st;//用来标识某个格子是否走过
    //         //2.创建一个可以存放每层相邻单元格的队列
    //         queue<pair<int,int>> q;

    //         q.push(make_pair(next_x,next_y));//从(0,0)点开始寻找pq中的值
    //         st.insert(make_pair(next_x,next_y));//标识(next_x,next_y)已经走过了

    //         //3.记录找到goal的最短路径
    //         int cnt=0,goal=v[k++];
    //         while(!q.empty())
    //         {
    //             cnt++;
    //             //每层单元格的个数
    //             int size=q.size();
    //             //判断相邻单元格能否入队列
    //             for(int i=0;i<size;i++)
    //             {
    //                 pair<int,int> pir=q.front();
    //                 q.pop();
    //                 //相邻单元格入队列
    //                 for(int j=0;j<4;j++)
    //                 {
    //                     int x=pir.first+arr_x[j],y=pir.second+arr_y[j];
    //                     if(x>=0 && x<forest.size() && y>=0 && y<forest[0].size() && st.count({x,y})==0  && forest[x][y]>=1)
    //                     {
    //                         //找到了目标树
    //                         if(forest[x][y]==goal)
    //                         {
    //                             forest[x][y]=1;
    //                             ret+=cnt;
    //                             next_x=x,next_y=y;//下次寻找下一个goal时，从此处开始寻找
    //                             goto start;
    //                         }
    //                         q.push(make_pair(x,y));
    //                         st.insert({x,y});
    //                     }
    //                 }
    //             }
    //         }
    //         //如果没有直接走到start,说明没找到goal,路被堵死了
    //         return -1;
    //     }
    //     return ret;
    // }

    int cutOffTree(vector<vector<int>>& forest) 
    {
        //题目要求:1.先砍低的树，再砍高的树;  2.将树砍倒后，单元格的值改为1;  3.0不能走，非0才能走
        //思路:bfs，队列每层存放"非0的相邻单元格",按值大小排升序,直到无路可走,判断树是否已经全部砍完
        
        //1.给所有树按高度排序
        vector<int> v;
        for(int i=0;i<forest.size();i++)
        {
            for(int j=0;j<forest[i].size();j++)
            {
                if(forest[i][j]>1) v.push_back(forest[i][j]);
            }
        }
        sort(v.begin(),v.end());
        
        //接下来,需要从forest中依次找到pq中的值,每次都按最小路径去找

        //2.记录所有v[i]的最短路径
        int ret=0,next_x=0,next_y=0;
        for(const auto& x:v)
        {
            int steps=my_bfs(forest,next_x,next_y,x);
            if(steps==-1)return -1;
            ret+=steps;
        }
        return ret;
    }

    //用来标识某个格子是否走过
    // set<pair<int,int>> st;  //超时，这题真贱呐!!!
    bool vis[51][51];
    int my_bfs(vector<vector<int>>& forest,int& next_x,int& next_y,int goal)
    {
        if(forest[next_x][next_y]==goal)return 0;

        // st.clear();
        memset(vis,0,sizeof(vis));

        //2.创建一个可以存放每层相邻单元格的队列
        queue<pair<int,int>> q;

        q.push(make_pair(next_x,next_y));//从(0,0)点开始寻找pq中的值
        // st.insert(make_pair(next_x,next_y));//标识(next_x,next_y)已经走过了
        vis[next_x][next_y]=1;

        //3.记录找到goal的最短路径
        int cnt=0;
        while(!q.empty())
        {
            cnt++;
            //每层单元格的个数
            int size=q.size();
            //判断相邻单元格能否入队列
            for(int i=0;i<size;i++)
            {
                pair<int,int> pir=q.front();
                q.pop();
                //相邻单元格入队列
                for(int j=0;j<4;j++)
                {
                    int x=pir.first+arr_x[j],y=pir.second+arr_y[j];
                    if(x>=0 && x<forest.size() && y>=0 && y<forest[0].size() && /*st.count({x,y})==0*/vis[x][y]==0  && forest[x][y]>=1)
                    {
                        //找到了目标树
                        if(forest[x][y]==goal)
                        {
                            next_x=x,next_y=y;//下次寻找下一个goal时，从此处开始寻找
                            return cnt;
                        }
                        q.push(make_pair(x,y));
                        // st.insert({x,y});
                        vis[x][y]=1;
                    }
                }
            }
        }
        //如果没有直接走到start,说明没找到goal,路被堵死了
        return -1;
    }
};